1. Field of the Invention
This invention relates generally to computer graphics and, more particularly, to a method for generating light values for a set of vertices.
2. Description of the Related Art
One of the principal goals of computer graphics is the rendering of realistic images (e.g., two- or three-dimensional images). Rendering images of real or imaginary objects typically involves generating geometric models (e.g., polygonal surfaces) of the objects and applying lighting effects to them. In computer graphics, surfaces of an object are generally modeled by a set of vertices that define graphics primitives such as polygons, edges, and/or vertices. These vertices may be produced from a variety of sources such as an application, tesselated NURBS surfaces, spheres, cones, etc. The vertices may be connected by edges and a sequence of edges or vertices may define one or more polygons.
Among others, rendering of realistic 3D graphics requires accurate and efficient modeling of 3D surfaces based upon the position, orientation, and characteristics of the surfaces and the light sources illuminating them. In particular, the interaction between lights and surfaces must be accurately modeled for rendering. Conventional computer graphics systems have implemented various illumination techniques to generate light values at individual pixels using an illumination or lighting model. For example, conventional lighting models typically model one or more lighting effects such as ambient light, diffuse reflection, and specular reflection, which are well known in the art. The ambient light effect accounts for a lighting effect resulting from multiple reflections of light from the surfaces present in a scene. The diffuse reflection accounts for reflection of light from a surface, especially a dull, matte surface while the specular reflection accounts for reflection of light off a shiny surface.
FIG. 1 illustrates a schematic diagram of vectors N, L, and H typically used in conventional illumination models. Vector L is a light direction vector pointing from a point P on a surface 100 to a light source, such as a light bulb. Vector N is the outward surface normal vector at point P. View vector V is a vector pointing from point P to a viewer. Vector H is a half-angle vector bisecting the angle formed by the light vector L and the eye vector V. The angle between the vectors N and H is defined as angle xcex8. The vectors L and H are referred to herein as light vectors. Since the half-angle vector H is essentially a sum of the vectors L and V, it is also known as sum vector S.
In diffuse reflection modeling, the reflected light from the surface point P falls off approximately uniformly as a function of an angle between the vectors N and L. The diffuse light fall-off in the diffuse reflection model is typically modeled by using a dot product term Nxc2x7L. In specular reflection modeling, on the other hand, the light reflected from surface point P is modeled as falling off exponentially as seen from a direction of view vector V. The fall-off is generally modeled by a dot product term (Nxc2x7H)s where s is a surface material""s specular-reflection coefficient.
The ambient, diffuse, and specular models are well known and are described in greater detail in Computer Graphics: Principles and Practice by James D. Foley et al., Addison-Wesley (1996), ISBN 0-201-84840-6, which is incorporated herein by reference and constitutes a portion of the background against which the present invention was developed. Additionally, the OpenGL(trademark) (versions 1.1 and 1.2) application programming interface (API) describes a particular lighting model that includes effects like spotlighting, diffuse light reflection, specular light reflection, and related parameters for implementing a model. The OpenGL(trademark) (versions 1.1 and 1.2) graphics application programming interface is commercially available from SGI, also known as Silicon Graphics, Inc., the assignee of the present application, and is incorporated herein by reference.
Conventional methods typically evaluate light color values at the vertices of primitives by computing the diffuse and specular term dot products. For example, the OpenGL(trademark) graphics application programming interface, version 1.1 determines a vertex color C by evaluating the lighting equation for each light source i as follows:   "AutoLeftMatch"                                                                        C                =                                  xe2x80x83                                ⁢                                                      emission                    material                                    +                                                            ambient                      light_model                                        *                                          ambient                      material                                                        +                                                                                                                          xe2x80x83                                ⁢                                                      ∑                                          i                      =                      0                                                              n                      -                      1                                                        ⁢                                                                                    (                                                  1                                                                                    k                              c                                                        +                                                                                          k                                l                                                            ⁢                              d                                                        +                                                                                          k                                q                                                            ⁢                                                              d                                2                                                                                                                                    )                                            i                                        *                                                                  (                        spotlighteffect                        )                                            i                                        *                                                                                                                                            xe2x80x83                                ⁢                                  [                                                                                    ambient                        light                                            *                                              ambient                        material                                                              +                                                                                                                                            xe2x80x83                                ⁢                                                                            (                                              max                        ⁢                                                  {                                                                                    L                              ·                              N                                                        ,                            0                                                    }                                                                    )                                        *                                          diffuse                      light                                        *                                          diffuse                      material                                                        +                                                                                                                                              xe2x80x83                                    ⁢                                                                                    (                                                  max                          ⁢                                                      {                                                                                          H                                ·                                N                                                            ,                              0                                                        }                                                                          )                                            shininess                                        *                                          specular                      light                                        *                                          specular                      material                                                        ]                                ⁢                i                                                                          Eq.  (1)                    
In Equation (1), the term 1/[kc+kld+kqd2] is also referred to as xe2x80x9cattenuation factor,xe2x80x9d where d is the distance between the position of a light source i and the vertex, kc represents constant attenuation, kl is linear attenuation, and kq represents quadratic attenuation. Those skilled in the art will recognize that Equation (1) may be evaluated for each light source i (e.g., local light source) illuminating a given vertex of a primitive.
It should be appreciated that Equation (1) may also be applied to a given pixel to compute a color value for the pixel. However, applying such equation to individual pixels in a primitive is typically prohibitively expensive in terms of cost and time. Hence, most conventional methods implement well known shading methods such as Gouraud shading and Phong illumination techniques to generate the color values for the individual pixels within the primitive. However, other illumination techniques are described in U.S. patent application Ser. No. 08/839,035, filed Apr. 23, 1997, entitled xe2x80x9cA Method and System for Real Time Illumination of Computer Generated Images,xe2x80x9d by Vimal Parikh et al. In addition, U.S. Pat. No. 5,659,671 entitled xe2x80x9cMethod and Apparatus for Shading Graphical Images in a Data Processing System,xe2x80x9d by Tannenbaum et al. also describes Phong lighting and shading methods. The disclosures of these references are incorporated herein by reference.
In implementing a light equation to evaluate light color values, conventional techniques have typically computed the light vectors L and H for each vertex in a polygon mesh describing a scene and for each light illuminating the vertex. Unfortunately, implementing conventional shading methods generally requires considerable computing resources to evaluate due to the complexity in evaluating the vectors in dot products Nxc2x7L and (Nxc2x7H) of the diffuse and specular terms. For example, conventional methods typically normalize (i.e., unitize) vectors N, L, and H for computing the dot products in a lighting equation such as Equation (1) described above. This is because the unit vectors are direction vectors having a magnitude of one. The dot product of two unit vectors allows determination of similarity in directions of the vectors. By way of example, the dot product of two normal vectors is equal to 1 when the vectors have the same direction and 0 when the vectors are perpendicular to each other.
However, the vector normalization is a costly process that requires numerous multiplication, addition, division, and inverse square root operations. For example, a unitized vector of L vector is evaluated by computing L/|L|=L/[Lxc2x7L]1/2=L/[Lx2+Ly2+Lz2]1/2, where Lx, Ly, and Lz are x, y, z components of the vector L, respectively. Using the normalized vectors, the diffuse term is computed by evaluating the dot product Nxc2x7L. Likewise, the specular term is also determined using the normalized vectors by evaluating the dot product Nxc2x7H raised to the shininess exponent, s. The diffuse and specular terms are then used in the above equation along with the other well-known variables to produce an intensity (e.g., light color) at a given pixel. Given that a polygon mesh may include hundreds or thousands of vertices, evaluating the diffuse and specular term vectors individually and independently at each of the vertices may be prohibitively costly and time consuming to implement in many computer graphics systems.
In view of the foregoing, what is needed is a method and system for efficiently evaluating the dot product terms in illumination models without computing the vectors in the dot product terms individually and independently for each of the vertices.
Broadly speaking, the present invention fills these needs by providing a method and system for generating light values for a set of vertices. It should be appreciated that the present invention can be implemented in numerous ways, including as a process, an apparatus, a system, a device, a method, or a computer readable medium. Several inventive embodiments of the present invention are described below.
In one embodiment, the present invention provides a method for generating light values for a set of vertices. In this method, a set of vertices describing a geometric object to be rendered is received. Each vertex has a coordinate and is associated with one or more vectors for evaluating a light value. Then, a vertex is selected from the set of vertices for computing a light value at the selected vertex. The light value at the selected vertex is associated with a light source having a coordinate. A selected vector for the selected vertex is then scaled by an inverse magnitude value of a corresponding vector that is associated with a neighboring vertex. The selected vector is scaled to generate an approximately normalized vector for the selected vector. The light value is then evaluated at the selected vertex using the approximately normalized vector such that an accurate normalized vector need not be computed for the selected vertex. In a preferred embodiment, the vectors are light vector L and/or half-angle vector H that are used in diffuse and specular terms of illumination models, respectively.
In another embodiment, a method is provided for generating a normalized vector for a first vector at a given position based on a second vector at a neighboring position. The method includes: (a) determining an inverse-magnitude of the second vector; (b) scaling the first vector for the given position by the inverse-magnitude of the second vector to generate an approximately normalized vector A for the first vector; (c) determining an acceptable error range for the approximately normalized vector A; (d) determining whether the approximately normalized vector A is within the acceptable error range; (e) if the approximately normalized vector A is within the acceptable error range, using the approximately normalized vector A as the normalized vector for the first vector; and (f) if the approximately normalized vector A is not within the acceptable error range, evaluating an accurate normalized vector and using the accurate normalized vector as the normalized vector for the first vector.
By thus using the scaling the selected vector with an inverse-magnitude of a vector associated with a neighboring vertex, the present invention generates an approximately normalized vector for evaluating the light value at the selected vertex. The determination of the approximately normalized vector leads to substantial savings in time and resources that otherwise would be required to compute the accurate normalized vector at the selected vertex. Given that a model may contain hundreds or even thousands of vertices, the savings in resources and time may be significant. Other aspects and advantages of the invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.